package main

import "fmt"

func solution(m int, s string) int {
	n := len(s)
	dp := make([][]int, n+1)
	for i := range dp {
		dp[i] = make([]int, m+1)
	}

	for i := 0; i <= n; i++ {
		for j := 0; j <= m; j++ {
			if i == 0 {
				// 空字符串可以通过插入操作形成"UCC"
				if j >= 3 {
					dp[i][j] = 1
				}
				continue
			}
			// 不进行任何操作
			if i >= 1 {
				dp[i][j] = dp[i-1][j]
			}
			// 尝试形成UCC子串
			if i >= 3 {
				// 计算需要多少次编辑才能让s[i-3:i]变成"UCC"
				cost := 0
				if s[i-3] != 'U' {
					cost++
				}
				if s[i-2] != 'C' {
					cost++
				}
				if s[i-1] != 'C' {
					cost++
				}
				if j >= cost {
					if dp[i-3][j-cost]+1 > dp[i][j] {
						dp[i][j] = dp[i-3][j-cost] + 1
					}
				}
			} else {
				// 处理i<3的情况，通过插入操作形成"UCC"
				cost := 3 - i // 需要插入的字符数
				if j >= cost {
					if dp[0][j-cost]+1 > dp[i][j] {
						dp[i][j] = dp[0][j-cost] + 1
					}
				}
			}
		}
	}

	max := 0
	for j := 0; j <= m; j++ {
		if dp[n][j] > max {
			max = dp[n][j]
		}
	}
	return max
}

func main() {
	fmt.Println(solution(3, "UCUUCCCCC") == 3) // true
	fmt.Println(solution(6, "U") == 2)         // true
	fmt.Println(solution(2, "UCCUUU") == 2)    // true
}
